﻿using AlgorithmInterview.Chapter03._01;

namespace AlgorithmInterview.Chapter03._08;

/// <summary>
/// 结点编号法
/// </summary>
public class Test02
{
    /// <summary>
    /// 找出结点在二叉树中的编号
    /// </summary>
    /// <param name="root"></param>
    /// <param name="node"></param>
    /// <param name="num"></param>
    /// <returns></returns>
    public static bool GetNo(BiTNode root, BiTNode node, IntRef number)
    {
        if (root == null)
            return false;
        if (root == node)
            return true;
        int tmp = number.Num;
        number.Num = 2 * tmp;
        if (GetNo(root.Lchild, node, number))
        {
            return true;
        }
        else
        {
            number.Num = tmp * 2 + 1;
            return GetNo(root.Rchild, node, number);
        }
    }

    /// <summary>
    /// 根据结点的编号找出对应的结点
    /// </summary>
    /// <param name="root"></param>
    /// <param name="number"></param>
    /// <returns></returns>
    public static BiTNode GetNodeFromNum(BiTNode root, int number)
    {
        if (root == null || number < 0)
            return null;
        if (number == 1)
            return root;
        int len = (int)(Math.Log(number) / Math.Log(2));
        // 去掉根结点表示的i
        number -= 1 << len;
        for (; len > 0; len--)
        {
            if (((1 << (len - 1)) & number) == 1)
            {
                root = root.Rchild;
            }
            else
            {
                root = root.Lchild;
            }
        }

        return root;
    }

    /// <summary>
    /// 查找二叉树中两个节点最近的共同父结点
    /// </summary>
    /// <param name="root"></param>
    /// <param name="node1"></param>
    /// <param name="node2"></param>
    /// <returns></returns>
    public static BiTNode FindParentNode(BiTNode root, BiTNode node1, BiTNode node2)
    {
        IntRef ref1 = new IntRef();
        ref1.Num = 1;
        IntRef ref2 = new IntRef();
        ref2.Num = 1;
        GetNo(root, node1, ref1);
        GetNo(root, node2, ref2);
        int num1 = ref1.Num;
        int num2 = ref2.Num;
        while (num1 != num2)
        {
            if (num1 > num2)
                num1 /= 2;
            else
            {
                num2 /= 2;
            }
        }

        return GetNodeFromNum(root, num1);
    }
}

public class IntRef
{
    public int Num { get; set; }
}